package com.qfedu.entity.course11;

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = new int[]{10, 11, 12, 13, 14, 15, 16, 17};
        int target = 10;
        int index = search(array, target);
        System.out.println(index);
    }

    public static int search(int[] array, int target) {
        //最小索引指针
        int min = 0;
        int max = array.length - 1;
        while (min <= max) {
            //算出平均索引位置
            int mid = (min + max) / 2;
            if (array[mid] == target) {
                return mid;
            }
            if (array[mid] < target) {
                min = mid + 1;
            }
            if (array[mid] > target) {
                max = mid - 1;
            }
        }
        return -1;
    }

    public static int searchRecursion(int[] nums, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        // 取正中间那个数的下标 middle。
        int middle = low + (high - low) / 2;
        // 判断一下正中间的那个数是不是要找的目标数 target，是，就返回下标 middle。
        if (nums[middle] == target) {
            return middle;
        }

        // 如果发现目标数在左边，就递归地从左半边进行二分搜索。
        if (target < nums[middle]) {
            return searchRecursion(nums, target, low, middle - 1);
        } else {
            return searchRecursion(nums, target, middle + 1, high);
        }//否则从右半边递归地进行二分搜索。
    }
}
